[Codeforces 1384 D]GameGame 题解

闲话:这场做出ACD可以到前百名.

原题链接:Codeforces 1384 D
题目大意:有两个人初始分数都是00,一共有nn个值aia_i.每一步操作可以让自己的分数和其中任意一个aia_i异或起来,并删掉这个aia_i.最后两边谁的值更大谁获胜.问先手是否必胜,或是平局.
数据范围:
1n1051 \leq n \leq 10^5
0ai1090 \leq a_i \leq 10^9

先把特殊情况抠掉:平局的时候两边的分数是相等的,因为两边的分数就是取两个不同的集合,整个集合的并集是原来的序列aa,交集是空集,所以两边的分数异或起来是00说明整个序列的异或和为00.因此整个序列异或和x=0x=0的时候,游戏为平局.
如果xx不为00.因为整个xx应该是两个数的异或和,即两边的分数的异或和,那么xx的某一位如果是11的话代表着有一边是11而有一边是00,也就是说,两边的分数在这一位上出现了不同,这一位就是决定了两边的分数谁更大的关键位置.假设这一位是ii,满足x >> i & 1这个表达式为真.显然两边的分数在这一位上是各取了原先aa序列里所有的数这一位上的数位值,再异或起来得到的(因为异或是不进位的,本位的值与其他位的元素无关),所以这一位上到底是先手分的11还是后手的分到11应该要看整个序列里的所有元素这一位上具体是多少.显然只有两种取值0011,分别记为c0c0c1c1.
多种情况,一个一个来分析:
①如果c1c1是偶数.
由于本位置上异或和应该是11,所以与之矛盾了,因为偶数个11必然组成00,而之后再有多少个00都不会让结果变得更大,因此这个情况其实是矛盾的.
②如果c1c1是奇数
在这个情况下,11的数量其实是有很大影响的,通过枚举可以发现,如果是奇数个11的话,实际上是有两种情况的:因为在有44的倍数个11和单个的11的时候,组合起来的异或值还是11,但是如果去掉44的倍数的部分之后,余的是3311,这个时候就会造成一个0010 \oplus 0 \oplus 1的情况,他们的异或和是00.这里要继续划分情况讨论.

1'如果c1%4=1c1 \% 4 = 1即余下11只有一个的情况.
在这种情形下,对于我这个先手的人来说,我只需要先拿掉一个11,那么接下来我要得到一个异或和是00的方案,接下来对手怎么做我就怎么做,这样的话,我手上是必然得到奇数个11和若干个个00的,这样结束之后,我手上偶数个11得到的就是00,最后多一个11,我就胜利了.
也就是说在1'这个情形下,先手是必胜的,因为他可以抢掉奇数的那一个11.

2'如果c1%4=3c1 \%4 = 3即余下11是有三个的情况.
这种情况可能就难看了一些,因为他是余下了三个.作为先手,还是按之前的策略来抢出一个奇数的11,但是此时后手完全可以仿照先手的镜像操作,来使先手得到偶数个的11.不过这一点不是总能实现的:假设当c0c0的个数是偶数的时候,由于是偶数,所以整个操作序列里可以把偶数的00的部分全部删去,只看留下的11的操作:既然是余数是33,那么整个局面除了44的倍数的部分,一定是一个111111的序列,即先手必然取到偶数个11导致手上是00.也就是说如果c0%2==0c0 \%2 == 0,此时就是必胜的.不过另外一种情况,也就是当c0c0的个数也是奇数的时候,会补齐操作序列里的数量,就是说此时局面又可以等价成11101110这个情况,那么我先手选择掉00的话,就可以做到必胜.此时对于先手来说又是一个必胜的.

综上,整个局面当且仅当c1%4=3c1 \%4 = 3c0%2==0c0 \% 2 == 0时后手必胜,其余情况先手必胜.

以上都是我的个人的思考过程,想通了之后,这个问题可以用抵消的考虑方式快速的得到结论,下面说明一下:
首先,偶数个11或者偶数个00必然得到00,对结果是没有影响的,所以局面可以等价的把他们删掉.因此第一种情况是完全不需要考虑的.
其次第二种情况里,也就是说c1c1是奇数的时候的时候,又有两种情况了:因为对于奇数情况来说,如果模4411,得到的是11,如果得到的是33,则是00.为什么会有这个问题?可以按消去的想法简单的想一下,就是说偶数的部分虽然是可以消掉的,但是不一定是完全能消的,比如在c1%4==3c1 \%4 == 3的前提下,如果00是偶数个,则偶数个00很显然是可以消掉而毫无影响,但是11不行,因为偶数个00消掉之后,先手的人在这里必然会拿到两个11,而不能直接按消去的办法直接把他变成11.从另外一个角度来说明,c1c1是奇数,但是也要看他去掉11之后有几个一对11,这里面有几对额外的一对11,决定了他最后是11还是00.这一点需要特别注意.在这之后第二种情况下就分别对应11111111101110两种情况了,情形简化之后就很好考虑了.剩下的实现也比较简单,就不多提了.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		int xs = 0;
		vector<int> a(n);
		for (auto &i : a)
		{
			cin >> i;
			xs ^= i;
		}
		if(!xs)	cout << "DRAW\n";
		else
		{
			for(int i = 31;i >= 0;--i)
			{
				int ch = xs >> i & 1;
				if(!ch)	continue;
				int c1 = 0,c0 = 0;
				for(auto& v : a)
				{
					if(v >> i & 1)	++c1;
					else ++c0;
				}
				if(c1 % 4 == 3 && c0 % 2 == 0)	cout << "LOSE\n";
				else cout << "WIN\n";
				break;
			}
		}
	}
    return 0;
}